P4939 Agent2

题目描述

作为一个 ENLIGHTENED行动指挥，自然不想看到这一点，于是他偷取到了那些经常 咕咕咕 的 Agent 的在下来 $N$ 天的 活动安排表，并且叫上了你来整理。在整理过程中，ENLIGHTENED行动指挥 对你说了 $M$ 条命令，命令操作如下。

1. 输入 $0,a,b$，这代表在第 $a$ 天到第 $b$ 天，有一名 Agent 要咕咕咕。
2. 输入 $1$ $a$，这代表 ENLIGHTENED行动指挥 询问你根据目前的信息，在第 $a$ 天有多少名 Agent 会咕咕咕。

作为同是不咕鸟的你，也想要惩戒那些经常 咕咕咕 的人，所以，请协助完成 ENLIGHTENED行动指挥 完成整理，并且在他每次询问时，输出正确的答案。

输入格式

第一行输入两个整数输 $N,M$，
下来 $M$ 行, 每行输入一个命令，命令格式见题目描述。

$1\le a,b\le N\le {10}^7,M\le 4\times {10}^5$

输出格式

对于每一次询问的操作，都要输出询问的答案。答案之间用换行隔开。

Solution

树状数组/线段树

这题要求内存 $\le 125MB$ 而线段树要开 $5\times {10}^7$ 的数组大小。超出了内存，而树状数组开 $2\times {10}^7$ 即可

用树状数组则能AC

const int N = 1e7;
int a[N];
struct Tree { //线段树区间加模板
    ll l, r, sum, add;
}tr[N << 2];
void solve() {
    int n, m;cin >> n >> m;
    build(1, 1, n);
    while (m--) {
        int op;cin >> op;
        if (op == 0) {
            int a, b;cin >> a >> b;change(1, a, b, 1);
        } else {
            int a;cin >> a;
            cout << query(1, a, a) << "\n";
        }
    }
}

用树状数组区修/点查模板

int n, m, s[10000010]; //差分的区间和
int lowbit(int x) { //提取x的低位2次幂数
    return x & -x;
}
void change(int x, int k) { //向后修
    while (x <= n) s[x] += k, x += lowbit(x);
}
int query(int x) { //向前查
    int t = 0;
    while (x) t += s[x], x -= lowbit(x);
    return t;
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int op, x, y;cin >> op >> x;
        if (op == 0) {
            cin >> y;
            change(x, 1); change(y + 1, -1); //差分
        } else {
            cout << query(x) << "\n";
        }
    }
}